// https://leetcode.cn/problems/combinations/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> tmp;

        dfs(1, n, k, tmp, ans);
        return ans;
    }

    void dfs(int index, int n, int k, vector<int>& tmp, vector<vector<int>>& ans) {
        if (tmp.size() == k) {
            ans.push_back(tmp);
            return;
        }

        if (tmp.size() + n - index + 1 < k) {
            return;
        }

        tmp.push_back(index);
        dfs(index + 1, n, k, tmp, ans);
        tmp.pop_back();

        dfs(index + 1, n, k, tmp, ans);
    }
};